package 链表与双指针.m03.d06.t02;

import 链表与双指针.ListNode;

import java.util.PriorityQueue;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>
        ((p1, p2) -> p1.val - p2.val);
        if (lists.length == 0) {
            return null;
        }
        for(int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                minHeap.add(lists[i]);
            }
        }
        ListNode head = null, cur = null;
        while(!minHeap.isEmpty()) {
            ListNode top = minHeap.poll();
            if(head == null) {
                cur = head = top;
            } else {
                cur.next = top;
                cur = top;
            }
            ListNode next = top.next;
            if (next != null) {
                minHeap.add(next);                
            }

        }
        return head;
    }
}